#include <bits/stdc++.h>

using namespace std;

#define in read()

typedef long long ll;

const int MAXN = 1e5+10;

struct edge{int v,w,nxt;}e[MAXN<<2];

int h[MAXN],n,k,dis[MAXN],cnt,v[MAXN];
bool vis[MAXN];

void link(int x,int y,int w){e[++cnt] = (edge){y,w,h[x]};h[x] = cnt;}

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + (ch ^ 48);
	return x * sgn;
}

void spfa(){
	memset(dis,0xcf,sizeof(dis));
	dis[0] = 0;queue<int> q;
	q.push(0); vis[0] = 1;
	while(q.size()){
		int x = q.front();q.pop();
		vis[x] = 0;v[x]++;
		if(v[x] > n) {
			puts("-1");exit(0);
		}
		for(int i = h[x];i;i = e[i].nxt){
			int y = e[i].v,w = e[i].w;
			if(dis[y] < dis[x] + w){
				dis[y] = dis[x] + w;
				if(!vis[y]) q.push(y);
			}
		}
	}
}

int main (){
	n = in,k = in;
	for(int i = 1;i <= k;i++){
		int x = in,a = in,b = in;
		switch(x){
		case 1 :
			link(a,b,0);
			link(b,a,0);
			break;
		case 2:
			if(a == b) {puts("-1");return 0;}
			link(a,b,1);
			break;
		case 3:
			link(b,a,0);
			break;
		case 4:
			if(a == b){puts("-1");return 0;}
			link(b,a,1);
			break;
		case 5:
			link(a,b,0);
			break;
		}
	}
	for(int i = n;i >= 1;i--) link(0,i,0);
	spfa();
	int mn = n;ll ans = 0;
	for(int i = 1;i <= n;i++) mn = min(dis[i],mn),ans += dis[i];
	ans += (ll)(1-mn) * n;
	printf("%lld\n",ans);
	return 0;
}
